// Fill out your copyright notice in the Description page of Project Settings.

#include "Algorithm/Quadtree/QuadTreeNode.h"
#include "Algorithm/Battery.h"
#include "Kismet/KismetMathLibrary.h"
#include "Kismet/KismetSystemLibrary.h"

bool QuadTreeNode::IsNotUsed()
{
	return isLeaf && objs.Num() <= 0;
}

bool QuadTreeNode::InterSection(FVector _OCenter, float _radian)
{
	// 取相对原点
	FVector v = _OCenter - center;
	float x = UKismetMathLibrary::Min(v.X, extend.X);
	x = UKismetMathLibrary::Max(x, -extend.X);
	float y = UKismetMathLibrary::Min(v.Y, extend.Y);
	y = UKismetMathLibrary::Max(y, -extend.Y);
	return (x - v.X) * (x - v.X) + (y - v.Y) * (y - v.Y) <= _radian * _radian;
}

bool QuadTreeNode::InterSection(FVector _point)
{
	return (_point.X >= center.X - extend.X && _point.X <= center.X + extend.X && _point.Y >= center.Y - extend.Y && _point.Y <= center.Y + extend.Y);
}

bool QuadTreeNode::InterSection(FVector _pMin, FVector _pMax, FVector _point)
{
	return (_point.X >= _pMin.X && _point.X <= _pMax.X && _point.Y >= _pMin.Y && _point.Y <= _pMax.Y);
}

void QuadTreeNode::InsertObj(ABattery* obj)
{
	objs.Add(obj);
	// 直接插入
	if (isLeaf && objs.Num() <= maxCount)
	{
		return;
	}
	float dx[4] = {1, -1, -1, 1};
	float dy[4] = {1, 1, -1, -1};
	// 超过上限个数，创建子节点;或者不再是叶子节点
	isLeaf = false;
	for (auto& item : objs)
	{
		for (int i = 0; i < 4; i++)
		{
			// 四个象限
			FVector p = center + FVector(extend.X * dx[i], extend.Y * dy[i], 0);
			FVector pMin = p.ComponentMin(center);
			FVector pMax = p.ComponentMax(center);
			if (InterSection(pMin, pMax, item->GetActorLocation()))
			{
				if (!child_node[i].IsValid())
				{
					root = root.IsValid() ? root : this->AsShared();
					child_node[i] = MakeShareable(new QuadTreeNode(pMin / 2 + pMax / 2, extend / 2, depth + 1, root));
				}
				child_node[i]->InsertObj(item);
				// 确保只在一个象限内
				break; 
			}
		}
	}
	// 确保非叶子节点不存
	objs.Empty();
}

void QuadTreeNode::DrawBound(float time, float thickness)
{
	if (worldObject)
	{
		FLinearColor drawColor = bInRange ? FLinearColor::Green : FLinearColor::Red;
		FVector drawCenter = center + (bInRange ? FVector(0, 0, 8) : FVector(0, 0, 5));
		UKismetSystemLibrary::DrawDebugBox(worldObject, drawCenter, extend + FVector(0, 0, 1), drawColor, FRotator::ZeroRotator, time, thickness);
	}
}

void QuadTreeNode::TraceObjectInRange(AActor* traceActor, float _radian)
{
	FVector _OCenter = traceActor->GetActorLocation();
	if (InterSection(_OCenter, _radian))
	{
		bInRange = true;
		if (isLeaf)
		{
			for (ABattery* obj : objs)
			{
				_OCenter.Z = obj->GetActorLocation().Z;
				bool bCanActive = FVector::Distance(_OCenter, obj->GetActorLocation()) <= _radian;
				obj->ActiveState(bCanActive, traceActor);
			}
		} else
		{
			for (auto& node : child_node)
			{
				if (node.IsValid())
				{
					node->TraceObjectInRange(traceActor, _radian);
				}
			}
		}
	} else
	{
		TraceObjectOutRange(_OCenter, _radian);
	}
}

void QuadTreeNode::TraceObjectOutRange(FVector _OCenter, float _radian)
{
	bInRange = false;
	for (ABattery* obj : objs)
	{
		{
			obj->ActiveState(false, nullptr);
		}
	}
	for (auto& node : child_node)
	{
		if (node.IsValid())
		{
			node->TraceObjectOutRange(_OCenter, _radian);
		}
	}
}

void QuadTreeNode::UpdateState()
{
	DrawBound(1 / UKismetSystemLibrary::GetFrameCount()); // 根据帧数绘制
	if (!isLeaf)
	{
		// 如果不是叶子节点，则递归到子树下去，如果子树为空，则回收该节点
		for (auto& node : child_node)
		{
			if (node.IsValid())
			{
				node->UpdateState();
				if (node->IsNotUsed())
				{
					node.Reset();
					node = nullptr;
				}
			}
		}

		int32 count = 4;
		for (auto& node : child_node)
		{
			if (!node.IsValid()) count--;
		}
		if (count == 0)
		{
			isLeaf = true;
		} else return;
	}
	if (isLeaf && objs.Num() > 0)
	{
		// 如果叶子节点，更新物体是否在区域内；不在区域则移出，并重新插入
		int32 i = 0;
		while (i < objs.Num())
		{
			if (!InterSection(objs[i]->GetActorLocation()))
			{
				ABattery* battery = objs[i];
				objs.Swap(i, objs.Num() - 1);
				objs.Pop();
				root->InsertObj(battery);
				continue;
			}
			i++;
		}
	}
}
